package algorithm.dynamicProgramming.p416;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 */
class Solution_v1 {
    // memo[i][c]表示使用索引为[0...i]的这些元素，是否可以完全填充一个容量为c的背包
    // -1 表示为未计算；0 表示不可以填充；1 表示可以填充
    private int[][] memo;

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 != 0) {
            return false;
        }

        memo = new int[nums.length][sum / 2 + 1];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], -1);
        }

        return tryPartition(nums, nums.length - 1, sum / 2);
    }

    // 使用nums[0...length]，是否可以完全填充一个容量为c的背包
    private boolean tryPartition(int[] nums, int index, int c) {
        if (c == 0) {
            return true;
        }
        // 装入的内容已经溢出了背包的容量或者没有数字可以选了
        if (c < 0 || index < 0) {
            return false;
        }

        if (memo[index][c] == -1) {
            memo[index][c] = (tryPartition(nums, index - 1, c) ||
                    tryPartition(nums, index - 1, c - nums[index])) ? 1 : 0;
        }

        return memo[index][c] == 1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().canPartition(new int[]{1, 5, 11, 5}));
    }
}